/**
 * Copyright (c) 2020-2024, huli.com
 * All rights reserved.
 */
package com.xiaohujr.xuexue.leetcode;

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * 最长上升子序列
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/
 *
 * @author Xue Xue (xuexue1@huli.com)
 * @version 1.0
 * @since 2020/8/26
 */
public class Q300 {

    public int lengthOfLIS(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }

        List<Integer> sumList = new LinkedList<>();
        for (int i = 1; i < nums.length; i++) {
            int sum = 1;
            int tmp = nums[i - 1];
            for (int j = i; j < nums.length; j++) {
                if (nums[j] > tmp) {
                    sum += 1;
                    tmp = nums[j];
                }
            }
            sumList.add(sum);
        }
        Collections.sort(sumList, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
        return sumList.get(sumList.size() - 1);
    }

    public static void main(String[] args) {
        System.out.println(new Q300().lengthOfLIS(new int[]{10,9,2,5,3,4}));
    }
}
